package com.sise.Backtracking;

/**
 *      剑指 Offer 13. 机器人的运动范围
 *
 *      地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 *      一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
 *      也不能进入行坐标和列坐标的数位之和大于k的格子。
 *      例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。
 *      但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 *      示例 1：
 *      输入：m = 2, n = 3, k = 1
 *      输出：3
 */
public class _offer_13_movingCount {

    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        return dfs(m, n, k, 0, 0);
    }

    private int dfs(int m, int n, int k, int i,int j){

        if (i > m - 1 || j > n - 1 || bitSum(i) + bitSum(j) > k || visited[i][j]) return 0;
        visited[i][j] = true;       // 由于这里是记录可达到的方格数，故此不能进行回溯
        return dfs(m, n, k,i + 1, j) + dfs(m, n, k, i, j + 1) + 1;      // 向下或向右走，+1 为本身格子
    }

    // 计算 x 的数位之和
    private int bitSum(int n) {
        int sum = 0;
        while(n > 0) {
            sum += n % 10;      // 取最后一位位数
            n /= 10;            // 除去 最后一位数
        }
        return sum;
    }
}
